#include<vector>
#include<iostream>
#include<unordered_map>
#include<algorithm>
using namespace std;


struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 
class Solution {
    TreeNode* constructFromPrePost(int pre_start,int pre_end, int post_start, int post_end, 
        vector<int>& pre, unordered_map<int, int>&postHashMap) {
        if (pre_start >= pre_end || post_start >= post_end) return NULL;
        TreeNode* node = new TreeNode(pre[pre_start++]);
        if (pre_start >= pre_end) return node;
        int split = postHashMap[pre[pre_start]] + 1;
        int len = split - post_start;
        node->left = constructFromPrePost(pre_start, pre_start + len, post_start, split, pre, postHashMap);
        node->right = constructFromPrePost(pre_start + len, pre_end, split, post_end - 1,pre, postHashMap);
        return node;
    }

public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        unordered_map<int, int>postHashMap;
        for (int i = 0; i < post.size(); ++i)
            postHashMap[post[i]] = i;
        TreeNode* root = constructFromPrePost(0, pre.size(), 0, post.size(), pre, postHashMap);
        return root;
    }
};

int main() {
    Solution sol;
    vector<int> pre = { 1,2,4,5,3,6,7 };
    vector<int> post = { 4,5,2,6,7,3,1 };
    sol.constructFromPrePost(pre, post);
}